home *** CD-ROM | disk | FTP | other *** search
/ Dr. Windows 3 / dr win3.zip / dr win3 / NEW_TECH / GREPS.ZIP / DFA.C < prev    next >
C/C++ Source or Header  |  1993-09-17  |  60KB  |  2,276 lines
  1. /* dfa.c - determinisitic extended regexp routines for GNU
  2.    Copyright (C) 1988 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. /* Written June, 1988 by Mike Haertel
  19.    Modified July, 1988 by Arthur David Olson to assist BMG speedups  */
  20.  
  21. #include <stdio.h>
  22. #include <assert.h>
  23.  
  24. #if defined(USG) || defined(STDC_HEADERS)
  25. #include <string.h>
  26. #ifndef index
  27. #define index strchr
  28. #endif
  29. #else
  30. #include <string.h>
  31. #endif
  32.  
  33. #include "dfa.h"
  34.  
  35. #if __STDC__
  36. typedef void *ptr_t;
  37. #else
  38. typedef char *ptr_t;
  39. #endif
  40.  
  41. static void    regmust();
  42.  
  43. static ptr_t
  44. xcalloc(n, s)
  45.      int n;
  46.      size_t s;
  47. {
  48.   ptr_t r = calloc(n, s);
  49.  
  50.   if (!r)
  51.     regerror("Memory exhausted");
  52.   return r;
  53. }
  54.  
  55. ptr_t                /* Not static, so alloca.o can use it.  */
  56. xmalloc(n)
  57.      size_t n;
  58. {
  59.   ptr_t r = malloc(n);
  60.  
  61.   assert(n != 0);
  62.   if (!r)
  63.     regerror("Memory exhausted");
  64.   return r;
  65. }
  66.  
  67. static ptr_t
  68. xrealloc(p, n)
  69.      ptr_t p;
  70.      size_t n;
  71. {
  72.   ptr_t r = realloc(p, n);
  73.  
  74.   assert(n != 0);
  75.   if (!r)
  76.     regerror("Memory exhausted");
  77.   return r;
  78. }
  79.  
  80. #define CALLOC(p, t, n) ((p) = (t *) xcalloc((n), sizeof (t)))
  81. #define MALLOC(p, t, n) ((p) = (t *) xmalloc((n) * sizeof (t)))
  82. #define REALLOC(p, t, n) ((p) = (t *) xrealloc((ptr_t) (p), (n) * sizeof (t)))
  83.  
  84. /* Reallocate an array of type t if nalloc is too small for index. */
  85. #define REALLOC_IF_NECESSARY(p, t, nalloc, index) \
  86.   if ((index) >= (nalloc))              \
  87.     {                          \
  88.       while ((index) >= (nalloc))          \
  89.     (nalloc) *= 2;                  \
  90.       REALLOC(p, t, nalloc);              \
  91.     }
  92.  
  93. #ifdef DEBUG
  94. #include <stdio.h>
  95.  
  96. static void
  97. prtok(t)
  98.      _token t;
  99. {
  100.   char *s;
  101.  
  102.   if (t < 0)
  103.     fprintf(stderr, "END");
  104.   else if (t < _NOTCHAR)
  105.     fprintf(stderr, "%c", t);
  106.   else
  107.     {
  108.       switch (t)
  109.     {
  110.     case _EMPTY: s = "EMPTY"; break;
  111.     case _BACKREF: s = "BACKREF"; break;
  112.     case _BEGLINE: s = "BEGLINE"; break;
  113.     case _ALLBEGLINE: s = "ALLBEGLINE"; break;
  114.     case _ENDLINE: s = "ENDLINE"; break;
  115.     case _ALLENDLINE: s = "ALLENDLINE"; break;
  116.     case _BEGWORD: s = "BEGWORD"; break;
  117.     case _ENDWORD: s = "ENDWORD"; break;
  118.     case _LIMWORD: s = "LIMWORD"; break;
  119.     case _NOTLIMWORD: s = "NOTLIMWORD"; break;
  120.     case _QMARK: s = "QMARK"; break;
  121.     case _STAR: s = "STAR"; break;
  122.     case _PLUS: s = "PLUS"; break;
  123.     case _CAT: s = "CAT"; break;
  124.     case _OR: s = "OR"; break;
  125.     case _LPAREN: s = "LPAREN"; break;
  126.     case _RPAREN: s = "RPAREN"; break;
  127.     default: s = "SET"; break;
  128.     }
  129.       fprintf(stderr, "%s", s);
  130.     }
  131. }
  132. #endif /* DEBUG */
  133.  
  134. /* Stuff pertaining to charsets. */
  135.  
  136. static int
  137. tstbit(b, c)
  138.      int b;
  139.      _charset c;
  140. {
  141.   return c[b / INTBITS] & 1 << b % INTBITS;
  142. }
  143.  
  144. static void
  145. setbit(b, c)
  146.      int b;
  147.      _charset c;
  148. {
  149.   c[b / INTBITS] |= 1 << b % INTBITS;
  150. }
  151.  
  152. static void
  153. clrbit(b, c)
  154.      int b;
  155.      _charset c;
  156. {
  157.   c[b / INTBITS] &= ~(1 << b % INTBITS);
  158. }
  159.  
  160. static void
  161. copyset(src, dst)
  162.      const _charset src;
  163.      _charset dst;
  164. {
  165.   int i;
  166.  
  167.   for (i = 0; i < _CHARSET_INTS; ++i)
  168.     dst[i] = src[i];
  169. }
  170.  
  171. static void
  172. zeroset(s)
  173.      _charset s;
  174. {
  175.   int i;
  176.  
  177.   for (i = 0; i < _CHARSET_INTS; ++i)
  178.     s[i] = 0;
  179. }
  180.  
  181. static void
  182. notset(s)
  183.      _charset s;
  184. {
  185.   int i;
  186.  
  187.   for (i = 0; i < _CHARSET_INTS; ++i)
  188.     s[i] = ~s[i];
  189. }
  190.  
  191. static int
  192. equal(s1, s2)
  193.      const _charset s1;
  194.      const _charset s2;
  195. {
  196.   int i;
  197.  
  198.   for (i = 0; i < _CHARSET_INTS; ++i)
  199.     if (s1[i] != s2[i])
  200.       return 0;
  201.   return 1;
  202. }
  203.  
  204. /* A pointer to the current regexp is kept here during parsing. */
  205. static struct regexp *reg;
  206.  
  207. /* Find the index of charset s in reg->charsets, or allocate a new charset. */
  208. static int
  209. charset_index(s)
  210.      const _charset s;
  211. {
  212.   int i;
  213.  
  214.   for (i = 0; i < reg->cindex; ++i)
  215.     if (equal(s, reg->charsets[i]))
  216.       return i;
  217.   REALLOC_IF_NECESSARY(reg->charsets, _charset, reg->calloc, reg->cindex);
  218.   ++reg->cindex;
  219.   copyset(s, reg->charsets[i]);
  220.   return i;
  221. }
  222.  
  223. /* Syntax bits controlling the behavior of the lexical analyzer. */
  224. static syntax_bits, syntax_bits_set;
  225.  
  226. /* Flag for case-folding letters into sets. */
  227. static case_fold;
  228.  
  229. /* Entry point to set syntax options. */
  230. void
  231. regsyntax(bits, fold)
  232.      int bits;
  233.      int fold;
  234. {
  235.   syntax_bits_set = 1;
  236.   syntax_bits = bits;
  237.   case_fold = fold;
  238. }
  239.  
  240. /* Lexical analyzer. */
  241. static const char *lexstart;    /* Pointer to beginning of input string. */
  242. static const char *lexptr;    /* Pointer to next input character. */
  243. static lexleft;            /* Number of characters remaining. */
  244. static caret_allowed;        /* True if backward context allows ^
  245.                    (meaningful only if RE_CONTEXT_INDEP_OPS
  246.                    is turned off). */
  247. static closure_allowed;        /* True if backward context allows closures
  248.                    (meaningful only if RE_CONTEXT_INDEP_OPS
  249.                    is turned off). */
  250.  
  251. /* Note that characters become unsigned here. */
  252. #define FETCH(c, eoferr)             \
  253.   {                         \
  254.     if (! lexleft)                 \
  255.       if (eoferr)                 \
  256.     regerror(eoferr);            \
  257.       else                     \
  258.     return _END;                 \
  259.     (c) = (unsigned char) *lexptr++;  \
  260.     --lexleft;                     \
  261.   }
  262.  
  263. static _token
  264. lex()
  265. {
  266.   _token c, c2;
  267.   int invert;
  268.   _charset cset;
  269.  
  270.   FETCH(c, (char *) 0);
  271.   switch (c)
  272.     {
  273.     case '^':
  274.       if (! (syntax_bits & RE_CONTEXT_INDEP_OPS)
  275.       && (!caret_allowed ||
  276.           (syntax_bits & RE_TIGHT_VBAR) && lexptr - 1 != lexstart))
  277.     goto normal_char;
  278.       caret_allowed = 0;
  279.       return syntax_bits & RE_TIGHT_VBAR ? _ALLBEGLINE : _BEGLINE;
  280.  
  281.     case '$':
  282.       if (syntax_bits & RE_CONTEXT_INDEP_OPS || !lexleft
  283.       || (! (syntax_bits & RE_TIGHT_VBAR)
  284.           && ((syntax_bits & RE_NO_BK_PARENS
  285.            ? lexleft > 0 && *lexptr == ')'
  286.            : lexleft > 1 && *lexptr == '\\' && lexptr[1] == ')')
  287.           || (syntax_bits & RE_NO_BK_VBAR
  288.               ? lexleft > 0 && *lexptr == '|'
  289.               : lexleft > 1 && *lexptr == '\\' && lexptr[1] == '|'))))
  290.     return syntax_bits & RE_TIGHT_VBAR ? _ALLENDLINE : _ENDLINE;
  291.       goto normal_char;
  292.  
  293.     case '\\':
  294.       FETCH(c, "Unfinished \\ quote");
  295.       switch (c)
  296.     {
  297.     case '1':
  298.     case '2':
  299.     case '3':
  300.     case '4':
  301.     case '5':
  302.     case '6':
  303.     case '7':
  304.     case '8':
  305.     case '9':
  306.       caret_allowed = 0;
  307.       closure_allowed = 1;
  308.       return _BACKREF;
  309.  
  310.     case '<':
  311.       caret_allowed = 0;
  312.       return _BEGWORD;
  313.  
  314.     case '>':
  315.       caret_allowed = 0;
  316.       return _ENDWORD;
  317.  
  318.     case 'b':
  319.       caret_allowed = 0;
  320.       return _LIMWORD;
  321.  
  322.     case 'B':
  323.       caret_allowed = 0;
  324.       return _NOTLIMWORD;
  325.  
  326.     case 'w':
  327.     case 'W':
  328.       zeroset(cset);
  329.       for (c2 = 0; c2 < _NOTCHAR; ++c2)
  330.         if (ISALNUM(c2))
  331.           setbit(c2, cset);
  332.       if (c == 'W')
  333.         notset(cset);
  334.       caret_allowed = 0;
  335.       closure_allowed = 1;
  336.       return _SET + charset_index(cset);
  337.  
  338.     case '?':
  339.       if (syntax_bits & RE_BK_PLUS_QM)
  340.         goto qmark;
  341.       goto normal_char;
  342.  
  343.     case '+':
  344.       if (syntax_bits & RE_BK_PLUS_QM)
  345.         goto plus;
  346.       goto normal_char;
  347.  
  348.     case '|':
  349.       if (! (syntax_bits & RE_NO_BK_VBAR))
  350.         goto or;
  351.       goto normal_char;
  352.  
  353.     case '(':
  354.       if (! (syntax_bits & RE_NO_BK_PARENS))
  355.         goto lparen;
  356.       goto normal_char;
  357.  
  358.     case ')':
  359.       if (! (syntax_bits & RE_NO_BK_PARENS))
  360.         goto rparen;
  361.       goto normal_char;
  362.  
  363.     default:
  364.       goto normal_char;
  365.     }
  366.  
  367.     case '?':
  368.       if (syntax_bits & RE_BK_PLUS_QM)
  369.     goto normal_char;
  370.     qmark:
  371.       if (! (syntax_bits & RE_CONTEXT_INDEP_OPS) && !closure_allowed)
  372.     goto normal_char;
  373.       return _QMARK;
  374.